
import random
import time

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        
        def backtrack(start, current_subset):
            # 添加当前子集到结果中（需要复制列表）
            result.append(current_subset[:])
            
            # 尝试添加后续元素
            for i in range(start, len(nums)):
                current_subset.append(nums[i])
                backtrack(i + 1, current_subset)
                current_subset.pop()
        
        backtrack(0, [])
        return result


class DataGenerator:
    """数据生成器类，用于生成测试用例"""
    
    @staticmethod
    def generate_random_array(size, min_val=-10, max_val=10):
        """生成随机不重复数组"""
        if size > (max_val - min_val + 1):
            raise ValueError("数组大小超过了可用范围内的不重复元素数量")
        
        nums = random.sample(range(min_val, max_val + 1), size)
        return nums
    
    @staticmethod
    def generate_sequential_array(size, start=1):
        """生成连续数组"""
        return list(range(start, start + size))
    
    @staticmethod
    def generate_test_cases():
        """生成多组测试用例"""
        test_cases = [
            # 基础测试用例
            [],
            [1],
            [1, 2],
            [1, 2, 3],
            
            # 负数测试用例
            [-1, 0, 1],
            [-3, -2, -1],
            
            # 较大数组测试用例
            [1, 2, 3, 4, 5],
            [-2, -1, 0, 1, 2, 3],
            
            # 随机生成的测试用例
            DataGenerator.generate_random_array(6, -5, 5),
            DataGenerator.generate_random_array(8, 0, 15),
            DataGenerator.generate_sequential_array(7, 10),
        ]
        return test_cases


def test_algorithm():
    """测试算法并输出结果"""
    solution = Solution()
    data_gen = DataGenerator()
    
    print("=" * 60)
    print("子集生成算法测试")
    print("=" * 60)
    
    test_cases = data_gen.generate_test_cases()
    
    for i, nums in enumerate(test_cases, 1):
        print(f"\n测试用例 {i}:")
        print(f"输入: {nums}")
        
        # 记录执行时间
        start_time = time.time()
        result = solution.subsets(nums)
        end_time = time.time()
        
        print(f"输出: {result}")
        print(f"子集数量: {len(result)}")
        print(f"期望子集数量: {2**len(nums)}")
        print(f"执行时间: {(end_time - start_time)*1000:.3f} ms")
        
        # 验证结果正确性
        if len(result) == 2**len(nums):
            print("✅ 测试通过")
        else:
            print("❌ 测试失败")


def performance_test():
    """性能测试"""
    solution = Solution()
    data_gen = DataGenerator()
    
    print("\n" + "=" * 60)
    print("性能测试")
    print("=" * 60)
    
    sizes = [5, 8, 10, 12, 15]
    
    for size in sizes:
        nums = data_gen.generate_sequential_array(size)
        
        start_time = time.time()
        result = solution.subsets(nums)
        end_time = time.time()
        
        execution_time = (end_time - start_time) * 1000
        
        print(f"数组大小: {size:2d} | "
              f"子集数量: {len(result):5d} | "
              f"执行时间: {execution_time:8.3f} ms | "
              f"内存估算: {len(result) * size * 4 / 1024:.2f} KB")


def generate_large_dataset():
    """生成大规模数据集用于压力测试"""
    data_gen = DataGenerator()
    
    print("\n" + "=" * 60)
    print("大规模数据集生成")
    print("=" * 60)
    
    # 生成不同规模的数据集
    datasets = {
        "small": [data_gen.generate_random_array(i, -10, 10) for i in range(1, 6)],
        "medium": [data_gen.generate_random_array(i, -20, 20) for i in range(6, 11)],
        "large": [data_gen.generate_random_array(i, -50, 50) for i in range(11, 16)]
    }
    
    for category, data_list in datasets.items():
        print(f"\n{category.upper()} 数据集:")
        for i, data in enumerate(data_list, 1):
            print(f"  数据集 {i}: {data}")
    
    return datasets


if __name__ == "__main__":
    # 运行基础测试
    test_algorithm()
    
    # 运行性能测试
    performance_test()
    
    # 生成大规模数据集
    datasets = generate_large_dataset()
    
    print("\n" + "=" * 60)
    print("测试完成")
    print("=" * 60)
